package datastructure.tree;

import java.util.Iterator;

/**
 * @author MaoLin Wang
 * @description TODO
 * @date 2020/8/26 8:42 上午
 */
public class IndexMinPQ<Key extends Comparable<? super Key>> implements Iterable<Integer> {

    private int[] pq;
    private int[] qp;
    private Key[] keys;
    private int currentSize;
    private int maxSize;

    public IndexMinPQ(int maxSize) {
        this.maxSize = maxSize;
        this.pq = new int[maxSize + 1];
        this.qp = new int[maxSize + 1];
        this.keys = (Key[]) new Comparable[maxSize + 1];
        for (int i = 0; i < maxSize; i++) {
            qp[i] = -1;
        }
    }

    public int minIndex() {
        if (!isEmpty()) {
            return pq[1];
        } else {
            return -1;
        }
    }

    public Key minKey() {
        if (!isEmpty()) {
            return keys[minIndex()];
        }
        return null;
    }

    public int delMin() {
        if (isEmpty()) {
            return -1;
        }
        int minIndex = minIndex();
        swapI(1, currentSize--);
        perDown(1);
        keys[minIndex] = null;
        qp[minIndex] = -1;
        return minIndex;
    }

    public void delete(int index) {
        checkIndex(index);
        if (contains(index)) {
            int i = qp[index];
            swapI(i, currentSize--);
            perUp(i);
            perDown(i);
            qp[i] = -1;
            keys[i] = null;
        }
    }

    private void perDown(int index) {
        int child;
        for (; index * 2 <= currentSize; index = child) {
            child = index * 2;
            if (child != currentSize && compareTo(child, child + 1) > 0) {
                child++;
            }
            if (compareTo(child, index) < 0) {
                swapI(child, index);
            }else {
                break;
            }
        }
    }

    public boolean isEmpty() {
        return currentSize == 0;
    }

    public void insert(int index, Key key) {
        checkIndex(index);
        if (contains(index)) {
            replace(index, key);
        } else {
            currentSize++;
            pq[currentSize] = index;
            qp[index] = currentSize;
            keys[index] = key;
            perUp(currentSize);
        }
    }

    private void perUp(int index) {
        for (; index > 1 && compareTo(index, index / 2) < 0; index /= 2) {
            swapI(index, index / 2);
        }
    }

    private void swapI(int p, int q) {
        int temp = pq[p];
        pq[p] = pq[q];
        pq[q] = temp;

        qp[pq[p]] = p;
        qp[pq[q]] = q;
    }

    private int compareTo(int p, int q) {
        return keys[pq[p]].compareTo(keys[pq[q]]);
    }

    private void replace(int index, Key key) {

    }

    public boolean contains(int index) {
        return qp[index] != -1;
    }

    private void checkIndex(int index) {
        if (index < 0 || index >= maxSize) {
            throw new IllegalArgumentException("参数越界");
        }
    }


    @Override
    public Iterator<Integer> iterator() {
        return null;
    }

    public static void main(String[] args) {
        String[] strings = {"a", "was", "the", "best", "of", "times", "it", "was", "the", "worst"};

        IndexMinPQ<String> pq = new IndexMinPQ<>(strings.length);
        for (int i = 0; i < strings.length; i++) {
            pq.insert(i, strings[i]);
        }

        System.out.println(pq.minIndex());
        System.out.println(pq.minKey());
        // delete and print each key
        //    pq.delete(3);
        while (!pq.isEmpty()) {
            int i = pq.delMin();
            System.out.println(i + " " + strings[i]);
        }
    }

    public void changeKey(int index, Key key) {
        checkIndex(index);
        if (contains(index)){
            keys[index]=key;
            perUp(qp[index]);
            perDown(qp[index]);
        }
    }
}
